package code;


public class ReverseNodes {
	 static public class ListNode {
		     int val;
		     ListNode next;
		     ListNode(int x) {
		         val = x;
		         next = null;
		     }
		 }
	 public ListNode reverseLinkedList(ListNode head){
		 ListNode pre2,pre,p;
		 pre=head;
		 p=head;
		 while(p!=null){
			 pre2=pre;
			 pre=p;
			 p=p.next;
			 if(pre2==pre){
				 pre2.next=null;
			 }
			 else{
				 pre.next=pre2;
			 }
		 }
		 head=pre;
		 return head;
	 }
    public ListNode reverseKGroup(ListNode head, int k) {
    	
    	if(head==null || head.next==null || k==1)	return head;
    	ListNode p,pre2,pre,start,tail,q,next;
    	
    	int cnt=1;
    	start=p=head;
    	tail=null;
    	pre2=head;
    	pre=head;
    	p=head;
    	cnt=0;
    	boolean flag=false;
    	while(p!=null){
//    		System.out.println(p.val);
    		pre2=pre;
    		pre=p;
    		p=p.next;
    		cnt++;
    		
    		if(pre2!=pre){
    			pre.next=pre2;
    		}
    		else pre2.next=null;
    		if(cnt%k==0){
    			flag=true;
    			if(cnt==k){
    				tail=head;
    				head=pre;
    				start=p;
    			}
    			else{
	    			tail.next=pre;
	    			tail=start;
	    			start=p;
    			}
    			pre=p;
    		}
    	}
    	pre=reverseLinkedList(pre);
    	if(flag)
    		tail.next=pre;
    	else head=pre;
//    	p=head;
//    	while(p!=null){
//    		System.out.print("-->"+p.val);
//    		p=p.next;
//    	}
//    	System.out.println();
        return head;
    }
	public static void main(String[] args){
		ListNode a=new ListNode(0);
		ListNode b=null,c=a;
		for(int i=1;i<10000;i++){
			if(b==null)	b=a;
			else c=b;
			b=new ListNode(i);
			c.next=b;
		}
		ReverseNodes rn=new ReverseNodes();
		rn.reverseKGroup(a, 1);
	}
}
